import itertools
def apriori(data, min_support):
    """
    Apriori算法实现函数
    :param data: 数据集，是一个二维列表，每一行代表一次购物记录（即一个事务），里面包含商品名称
    :param min_support: 最小支持度阈值
    :return: 频繁项集列表
    """
    # 第一步：获取所有的单个商品（即1-项集）并计算支持度
    itemset_1 = []
    support_count = {}
    for transaction in data:
        for item in transaction:
            if [item] not in itemset_1:
                itemset_1.append([item])
                support_count[frozenset([item])] = 0
            support_count[frozenset([item])] += 1
    num_transactions = len(data)
    frequent_1_itemsets = []
    for itemset in itemset_1:
        support = support_count[frozenset(itemset)] / num_transactions
        if support >= min_support:
            frequent_1_itemsets.append(itemset)
    # 存储所有的频繁项集
    all_frequent_itemsets = [frequent_1_itemsets]
    k = 2
    while all_frequent_itemsets[-1]:
        # 由上一轮的频繁k-1项集生成候选k项集
        candidate_k_itemsets = generate_candidates(all_frequent_itemsets[-1], k)
        support_count = {}
        for transaction in data:
            # 找出事务中包含的候选k项集并统计支持度
            subsets = [frozenset(candidate) for candidate in candidate_k_itemsets if all(x in transaction for x in candidate)]
            for subset in subsets:
                if subset not in support_count:
                    support_count[subset] = 0
                support_count[subset] += 1
        # 根据支持度筛选出频繁k项集
        frequent_k_itemsets = []
        for candidate in candidate_k_itemsets:
            support = support_count[frozenset(candidate)] / num_transactions
            if support >= min_support:
                frequent_k_itemsets.append(candidate)
        all_frequent_itemsets.append(frequent_k_itemsets)
        k += 1
    return all_frequent_itemsets

def generate_candidates(last_frequent_itemsets, k):
    """
    由上一轮的频繁项集生成候选k项集
    :param last_frequent_itemsets: 上一轮的频繁项集
    :param k: 当前要生成的项集的长度（k个元素的项集）
    :return: 候选k项集列表
    """
    candidates = []
    for i in range(len(last_frequent_itemsets)):
        for j in range(i + 1, len(last_frequent_itemsets)):
            union = list(set(last_frequent_itemsets[i]) | set(last_frequent_itemsets[j]))
            if len(union) == k:
                candidates.append(union)
    return candidates

# 模拟的购物数据集，每一行代表一次购物记录（事务），里面包含购买的商品名称
data = [
    ["牛奶", "面包", "鸡蛋"],
    ["面包", "鸡蛋", "黄油"],
    ["牛奶", "鸡蛋", "黄油"],
    ["牛奶", "面包"],
    ["面包", "鸡蛋"]
]
min_support = 0.4  # 最小支持度阈值，可以根据实际情况调整
frequent_itemsets = apriori(data, min_support)
for i, itemsets in enumerate(frequent_itemsets):
    print(f"频繁{i + 1}-项集:")
    for itemset in itemsets:
        print(list(itemset))